package com.example.sorts13.sort;

/**
 * @description
 * @auther lijiewei
 * @date 2021/8/30 20:48
 */
public class BucketSort {

    /**
     * 桶排序
     * @param arr 数组
     * @param bucketSize 桶容量
     * @return
     * @author lijiewei
     * @date   2021/8/30 20:51
     */
    public static void bucketSort(int[] arr, int bucketSize) {
        if (arr.length < 2) {
            return;
        }
        //数组最小值
        int minValue = arr[0];
        //数组最大值
        int maxValue = arr[1];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < minValue) {
                minValue = arr[i];
            } else if (arr[i] > maxValue) {
                maxValue = arr[i];
            }
        }

        //桶数量
        int bucketCount = (maxValue-minValue)/bucketSize + 1;
        int[][] buckets = new int[bucketCount][bucketSize];
        //记录每个桶里放了多少元素
        int[] indexArr = new int[bucketCount];

        //将数组中元素分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int bucketIndex = (arr[i] - minValue) / bucketSize;
            //满了需要扩容
            if (indexArr[bucketIndex] == buckets[bucketIndex].length) {
                ensureCapacity(buckets, bucketIndex);
            }
            buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i];
        }

        //对每个桶排序(快排序)
        int k = 0;
        for (int i = 0; i < buckets.length; i++) {
            if (indexArr[i] == 0) {
                continue;
            }
            quickSort(buckets[i], 0, indexArr[i] - 1);
            for (int j = 0; j < indexArr[i]; j++) {
                arr[k++] = buckets[i][j];
            }
        }
    }



    /**
     * 数组扩容
     * @param buckets 二维数组
     * @param bucketIndex 一维下标
     * @return
     * @author lijiewei
     * @date   2021/8/30 21:04
     */
    private static void ensureCapacity(int[][] buckets, int bucketIndex) {
        int[] tmpArr = buckets[bucketIndex];
        int[] newArr = new int[tmpArr.length * 2];
        for (int i = 0; i < tmpArr.length; i++) {
            newArr[i] = tmpArr[i];
        }
        buckets[bucketIndex] = newArr;
    }

    /**
     * 开始排序
     * @param arr 数组
     * @param p 开始下标
     * @param r 结束下标
     * @return
     * @author lijiewei
     * @date   2021/8/30 21:13
     */
    private static void quickSort(int[] arr, int p, int r) {
        if (p >= r) {
            return;
        }
        //分区，返回分区位下标
        int q = partition(arr, p, r);
        quickSort(arr, p, q-1);
        quickSort(arr, q+1, r);
    }

    /**
     * 分区
     * @param arr 数组
     * @param p 开始下标
     * @param r 结束下标
     * @return
     * @author lijiewei
     * @date   2021/8/30 21:16
     */
    private static int partition(int[] arr, int p, int r) {
        int pivot = arr[r];
        //i 左边小于pivot, i 右边（包括i）大于等于pivot
        int i = p;
        for (int j = p; j < r; j++) {
            if (arr[j] < pivot) {
                if (i != j) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
                i++;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[r];
        arr[r] = tmp;
        return i;
    }

    private static void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }

        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}

